/**
 * @author: Robert Hovhanessian
 * @CIN:    220379508
 */
/*
 * Although  tested and seems to be working fine, i think the code still needs some improvements.
 * I think restructuring the HSearch itself along with the deduction rules is in order. 
 */

package Hsearch;

import game.*;
import players.Player;

import java.util.ArrayList;
import java.util.List;


public class HSearch {
   private HexBoard board;
   private Player CurrPlayer, Player2;
   private List<Subgame> strong_subgames=new ArrayList<Subgame>();
   private List<Subgame> weak_subgames=new ArrayList<Subgame>();
   
   
   
   public HSearch() {
	   	// do nothing
   }
   public HexBoard SearchConnections(HexBoard hexBoard){
	   // get a copy of the board
	   this.board=hexBoard.clone();
	   
	   // make suere players are initialized
	   Player2=board.getLastMove().getPlayer();
	   this.CurrPlayer=board.getOtherPlayer( Player2 ); 

	   // do hsearch
	   DoHSearch(this.CurrPlayer);
	   DoHSearch(this.Player2); //do hsearch for 2nd player subgames (1st player has already merged the results)
	   
	   // return connected board
	   return this.board;
   }
   public void DoHSearch(Player ConnPlayer){
	   int strongcounter,weakcounter;
	   
	   // make sure lists are initialized
	   strong_subgames=new ArrayList<Subgame>();
	   weak_subgames=new ArrayList<Subgame>();
	   
	   // generate initial subgames to run the hsearch on
	   generateAllSubgames(ConnPlayer);
	   

	   Subgame s1, s2,w1;
	   
	   
	   // apply AndRules
	   strongcounter=0;
	   while (this.strong_subgames.size()>1 && strongcounter<this.strong_subgames.size() ){
			  s1=this.strong_subgames.remove(0);
			  s2=this.getMatchingStrong(s1);
			  if(s2!=null){
				  strongcounter=0;// reset counter
				  AndRule(s1,s2);
			  }else{
				  this.strong_subgames.add(s1);
				  strongcounter++;
			  }
	   };
	   
	   // apply OrRules to remaining weak_subgames
	   weakcounter=0;
	   while(this.weak_subgames.size()>1 && weakcounter<this.weak_subgames.size()){
		   w1=this.weak_subgames.remove(0);
		   OrRule(w1);
		   weakcounter++;
	   }

	   MergeStrongsOntoBoard(ConnPlayer);
	
   }

   public void AndRule(Subgame A, Subgame B){
	   Subgame s1;
	   
	   if(A.getX().equals( B.getX() ) ){
		   if(getIntersection(A.getC(),B.getC()).size()==0 && getIntersection(A.getY(),B.getY()).size()==0){
			   if(  board.isEmpty( A.getX().get(0) )  ){
				   s1=new Subgame(A.getY(),getUnion(A.getX(), getUnion(A.getC(),B.getC()) ),B.getY() );
				   OrRule(s1);
			   }else{
				   s1=new Subgame(A.getY(),getUnion(A.getC(),B.getC()),B.getY());
				   this.strong_subgames.add(s1);
			   }
		   }
	   }else if( A.getX().equals(B.getY()) ){
		   if(getIntersection(A.getC(),B.getC()).size()==0 && getIntersection(A.getY(),B.getX()).size()==0){
			   if(  board.isEmpty( A.getX().get(0) )  ){
				   s1=new Subgame(A.getY(),getUnion(A.getX(), getUnion(A.getC(),B.getC()) ),B.getX());
				   OrRule(s1);
			   }else{
				   s1=new Subgame(A.getY(),getUnion(A.getC(),B.getC()),B.getX());
				   this.strong_subgames.add(s1);
			   }
		   }
	   }else if(A.getY().equals(B.getX())){
		   if(getIntersection(A.getC(),B.getC()).size()==0 && getIntersection(A.getX(),B.getY()).size()==0){
			   if(  board.isEmpty( A.getY().get(0) )  ){
				   s1=new Subgame(A.getX(),getUnion(A.getY(), getUnion(A.getC(),B.getC()) ),B.getY());
				   OrRule(s1);
			   }else{
				   s1=new Subgame(A.getX(),getUnion(A.getC(),B.getC()),B.getY());
				   this.strong_subgames.add(s1);
			   }
		   }
	   }else if(A.getY().equals(B.getY())){
		   if(getIntersection(A.getC(),B.getC()).size()==0 && getIntersection(A.getX(),B.getX()).size()==0){
			   if(  board.isEmpty( A.getY().get(0) )  ){
				   s1=new Subgame(A.getX(),getUnion(A.getY(), getUnion(A.getC(),B.getC()) ),B.getX());
				   OrRule(s1);
			   }else{
				   s1=new Subgame(A.getX(),getUnion(A.getC(),B.getC()),B.getX());
				   this.strong_subgames.add(s1);
			   }
		   }
	   } // end i
   } // end AndRule
   
   public void OrRule(Subgame A){
	   int counter=0;
	   Subgame B;
	   
	   do{
		   B=getMatchingWeak(A);
		   if(B!=null){
			  A= new Subgame(A.getX(),getUnion(A.getC(),B.getC()),A.getY());
			  counter++; 
		   }
	   }while(B!=null);
	   
	   if(counter>=1){
		   this.strong_subgames.add( A );
	   }else if(counter==0){
		   this.weak_subgames.add(A);
	   }
   }// end OrRule

   
   private Subgame getMatchingStrong(Subgame s1){// given a strong subgame, finds a strong with common x or y (not both)
	   ArrayList<Cell> x,y=new ArrayList<Cell>();
	   boolean blnSameGroupSubgames=false;
	   
	   for(int i=0;i<this.strong_subgames.size();i++){
		   x=(ArrayList<Cell>)this.strong_subgames.get(i).getX();
		   //A =(ArrayList<Cell>)this.strong_subgames.get(i).getC(); // don't need this
		   y=(ArrayList<Cell>)this.strong_subgames.get(i).getY();
		   //blnSameGroupSubgames=(s1.getX().equals(x) && s1.getY().equals(y)) || (s1.getX().equals(y) && s1.getY().equals(x));

		   
		   if( s1.getX().equals(x) ){
			   if( board.isEmpty(s1.getY().get(0))==false && board.isEmpty(y.get(0))==false)
				   return this.strong_subgames.remove(i);
		   }else if( s1.getX().equals(y) ){
			   if( board.isEmpty(s1.getY().get(0))==false && board.isEmpty(x.get(0))==false)
				   return this.strong_subgames.remove(i);
		   }else if( s1.getY().equals(x) ){
			   if( board.isEmpty(s1.getX().get(0))==false && board.isEmpty(y.get(0))==false)
				   return this.strong_subgames.remove(i);
		   }else if(s1.getY().equals(y)){
			   if( board.isEmpty(s1.getX().get(0))==false && board.isEmpty(x.get(0))==false)
				   return this.strong_subgames.remove(i);
		   }

	   }

	   
	   return null;
   }
   
   private Subgame getMatchingWeak(Subgame s1){// given a weak subgame find another weak subgame with common targets and no common carriers
	   ArrayList<Cell> x,B,y=new ArrayList<Cell>();
	   
	   for(int i=0;i<this.weak_subgames.size();i++){
		   x=(ArrayList<Cell>)this.weak_subgames.get(i).getX();
		   B =(ArrayList<Cell>)this.weak_subgames.get(i).getC();
		   y=(ArrayList<Cell>)this.weak_subgames.get(i).getY();
		   if( (s1.getX().equals(x) && s1.getY().equals(y)) || (s1.getX().equals(y) && s1.getY().equals(x))  ){
			   if( getIntersection(s1.getC(),B ).size()==0 )
				   return this.weak_subgames.remove(i);
		   }
	   }
	   return null;
   }
   
   // MergeStrongsOntoBoard
   private void MergeStrongsOntoBoard(Player ConnPlayer){
	   for(Subgame s:this.strong_subgames){
		   if( board.isEmpty( s.getX().get(0) ) || board.isEmpty( s.getY().get(0) )){
			   // do nothing
		   }else{
			   // merge
			   for(Cell c: s.getC()){
				   board.setCell( new Cell(c.getX(),c.getY(),ConnPlayer) );
			   }
		   }
	   }
   }
   
   // generate all initial subgames before applying AND/OR rules
   private void generateAllSubgames(Player ConnPlayer){// generates all weak/strong subgames for each group. Called once before deductions start
	   ArrayList<ArrayList<Cell>> Groups=getGroups(ConnPlayer);
	   ArrayList<Cell> Group;

	   while (Groups.size()>0) {
			Group = Groups.remove(0);
			// now find subgames involving Group with any other group
			for (Cell cell : Group) {
				addSubgames(Groups,Group, cell); // find subgames that involve this cell in the group
			}
		}
	   //System.out.println("Initial Subgames:" + ConnPlayer + " Strong=" + this.strong_subgames.size() + " Weak=" + this.weak_subgames.size() );
	   
   }
   private void addSubgames(ArrayList<ArrayList<Cell>> groups,ArrayList<Cell> group, Cell cell){// helper for generateAllSubgames
		ArrayList<Cell> T,TL,TR,B,BL,BR;
					    T=getTop(cell);
						TL=getTopL(cell);
						TR=getTopR(cell);
						B=getBottom(cell);
						BL=getBottomL(cell);
						BR=getBottomR(cell);
		ArrayList<Cell> x_T,x_TL,x_TR,x_B,x_BL,x_BR;
		ArrayList<Cell> carrier;
		
		if(groups.size()==0)
			groups.add(new ArrayList<Cell>()); // this is a fix so that subgames connecting cells of last group to empty cells will also be generated
		
		for(ArrayList<Cell> grp: groups){ // checks group against each grp from the rest of the groups
			
			
			// find subgames involving top
			if( isEmptyGroup(T) && T.size()==2  ){
				x_T=this.getIntersection( getTop(T.get(0)) , getTop(T.get(1)) );
				if(x_T.size()==1){
					if( board.isEmpty( x_T.get(0) ) ){
					   this.addStrongSub( new Subgame(x_T,T,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:T){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(T,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									
									this.addWeakSub(   new Subgame( grp, getIntersection(T,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_T.get(0)) ){
					   this.addStrongSub( new Subgame(grp,T,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:T){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(T,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(T,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			
			// find subgames involving top-left
			if( isEmptyGroup(TL) && TL.size()==2  ){
				x_TL=this.getIntersection( getTopL(TL.get(0)) , getTopL(TL.get(1)) );
				if(x_TL.size()==1){
					if( board.isEmpty( x_TL.get(0) ) ){
					   this.addStrongSub( new Subgame(x_TL,TL,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:TL){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(TL,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									this.addWeakSub(   new Subgame( grp, getIntersection(TL,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_TL.get(0)) ){
					   this.addStrongSub( new Subgame(grp,TL,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:TL){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(TL,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(TL,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			
			// find subgames involving top-right
			if( isEmptyGroup(TR) && TR.size()==2  ){
				x_TR=this.getIntersection( getTopR(TR.get(0)) , getTopR(TR.get(1)) );
				if(x_TR.size()==1){
					if( board.isEmpty( x_TR.get(0) ) ){
					   this.addStrongSub( new Subgame(x_TR,TR,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:TR){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(TR,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									this.addWeakSub(   new Subgame( grp, getIntersection(TR,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_TR.get(0)) ){
					   this.addStrongSub( new Subgame(grp,TR,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:TR){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(TR,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(TR,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			// find subgames involving bottom
			if( isEmptyGroup(B) && B.size()==2  ){
				x_B=this.getIntersection( getBottom(B.get(0)) , getBottom(B.get(1)) );
				if(x_B.size()==1){
					if( board.isEmpty( x_B.get(0) ) ){
					   this.addStrongSub( new Subgame(x_B,B,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:B){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(B,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									this.addWeakSub(   new Subgame( grp, getIntersection(B,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_B.get(0)) ){
					   this.addStrongSub( new Subgame(grp,B,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:B){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(B,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(B,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			// find subgames involving bottom-left
			if( isEmptyGroup(BL) && BL.size()==2  ){
				x_BL=this.getIntersection( getBottomL(BL.get(0)) , getBottomL(BL.get(1)) );
				if(x_BL.size()==1){
					if( board.isEmpty( x_BL.get(0) ) ){
					   this.addStrongSub( new Subgame(x_BL,BL,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:BL){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(BL,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									this.addWeakSub(   new Subgame( grp, getIntersection(BL,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_BL.get(0)) ){
					   this.addStrongSub( new Subgame(grp,BL,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:BL){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(BL,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(BL,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			// find subgames involving bottom-right
			if( isEmptyGroup(BR) && BR.size()==2  ){
				x_BR=this.getIntersection( getBottomR(BR.get(0)) , getBottomR(BR.get(1)) );
				if(x_BR.size()==1){
					if( board.isEmpty( x_BR.get(0) ) ){
					   this.addStrongSub( new Subgame(x_BR,BR,group) );
					   
					   // get flower situation (i call it flower)
						for(Cell c:BR){ // this will happen twice
							for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
								if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
									carrier = new ArrayList<Cell>();
									carrier.add(c);
									// use getIntersection(BR,carrier) ,group) to get a new arraylist sized 1. otherwise u get a pointer clone
									this.addWeakSub(   new Subgame( grp, getIntersection(BR,carrier) ,group)  );
								}
							}
						}
					}else if( grp.contains(x_BR.get(0)) ){
					   this.addStrongSub( new Subgame(grp,BR,group) );
					}// otherwise it's connecting to a group belonging to other player. so ignore.
				}
			}else{
				for(Cell c:BR){ 
					if(board.isEmpty(c)){ // this will happen only once. or not at all.
						for(Cell nbr:board.getCellNeighbors(c)){ // check neibours of the empty cell
							if(grp.contains(nbr)){ // if a neibor of the empty cell is in another group
								carrier = new ArrayList<Cell>();
								carrier.add(c);
								// use getIntersection(BR,carrier) ,group) to get a new arraylist. otherwise u get a pointer clone
								this.addWeakSub(   new Subgame( grp, getIntersection(BR,carrier) ,group)  );
							}
						}  
					}
				}
			}
			
			
			// end find subgames
			
			
			
		}
		
		

		
		
   }

   //6 getter functions that help a cell find bridge. Adds cells in clockwise order(not important yet)
   private ArrayList<Cell> getTop(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();
	    
	    // x , y-1
	    if (y-1 >=0)
	      result.add(board.getCell(x, y-1)) ;

	    // x + 1 , y-1
	    if ( x + 1 <board.getSize() && y-1>=0)
	      result.add(board.getCell(x+1, y-1));
	   return result;
   }
   private ArrayList<Cell> getTopL(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();
	    
	    // x -1 , y
	    if ( x - 1>=0)
	      result.add(board.getCell(x-1, y));

	    // x , y-1
	    if (y-1 >=0)
	      result.add(board.getCell(x, y-1)) ;
	   return result;
   }
   private ArrayList<Cell> getTopR(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();
	    
	    // x + 1 , y-1
	    if ( x + 1 <board.getSize() && y-1>=0)
	      result.add(board.getCell(x+1, y-1));

	    // x + 1 , y
	    if ( x + 1<board.getSize())
	      result.add(board.getCell(x+1, y));
	   return result;
   }
   private ArrayList<Cell> getBottom(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();
	    
	    // x , y+1
	    if (y+1 <board.getSize())
	      result.add(board.getCell(x, y+1)) ;

	    // x - 1 , y+1
	    if ( x - 1>=0 && y+1<board.getSize())
	      result.add(board.getCell(x-1, y+1));
	   return result;
   }
   private ArrayList<Cell> getBottomL(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();

	    // x - 1 , y+1
	    if ( x - 1>=0 && y+1<board.getSize())
	      result.add(board.getCell(x-1, y+1));
	    
	    // x-1 , y
	    if (x-1 >=0)
	      result.add(board.getCell(x-1, y)) ;
	   return result;
   }
   private ArrayList<Cell> getBottomR(Cell cell){
	    ArrayList<Cell> result = new ArrayList<Cell>() ;
	    
	    int x = cell.getX();
	    int y = cell.getY();
	    
	    // x+1 , y
	    if (x+1 <board.getSize())
	      result.add(board.getCell(x+1, y)) ;

	    // x  , y+1
	    if (y+1<board.getSize())
	      result.add(board.getCell(x, y+1));
	   return result;
   }
   
  
   
   // helper function. Checks if all the cells in a group are empty. Useful for finding bridges
   private boolean isEmptyGroup(ArrayList<Cell> g){ // check if a given group is composed of all empty cells
	   for(Cell c: g){
		   if(board.isEmpty(c)==false)
			   return false;
	   }
	   return true;
   }
   // helper function. Checks if there's an empty cell in the group. Useful for finding bridges
   private boolean hasEmptyCell(ArrayList<Cell> g){ // check if there's an empty cell in a given group
	   for(Cell c: g){
		   if(board.isEmpty(c))
			   return true;
	   }
	   return false;
   }
   
   
   // add subgames to lists. do not add if duplicate subgame exists (called from addSubgames)
   private boolean addStrongSub(Subgame s){// checks for duplicates and adds strong subgames
	   if(this.strong_subgames.contains(s)==false){
		   this.strong_subgames.add(s);
		   return true;
	   }
		   
	   return false;
   }
   private boolean addWeakSub(Subgame s){// checks for duplicates and adds weak subgame
	   if(this.weak_subgames.contains(s)==false){
		   this.weak_subgames.add(s);
		   return true;
	   }
	   return false;
   }
   
   
   // search union/intersection functions
   public ArrayList<Cell> getIntersection(ArrayList<Cell> x ,ArrayList<Cell> y){// Intersection of cell groups
	   ArrayList<Cell> Intersection = new ArrayList<Cell>();
	   for(Cell c:x){
		   if(y.contains(c))
			  Intersection.add(c);
	   }
	   return Intersection;
   }
   public ArrayList<Cell> getUnion(ArrayList<Cell> x,ArrayList<Cell> y){// union of cell groups
	   ArrayList<Cell> Union = new ArrayList<Cell>();
	   Union.addAll(x);
	   Union.addAll(y);
	   return Union;
   }
   
   
   // initially generates groups of given player cells
   private ArrayList<ArrayList<Cell>> getGroups(Player player){// given a player, returns all groups of that player
	   ArrayList<Cell> visitedCells=new ArrayList<Cell>();
	   ArrayList<ArrayList<Cell>> groups=new ArrayList<ArrayList<Cell>>(); // list of group of cells
	   ArrayList<Cell> group;
	   
	   for(int i=0;i<board.getSize();i++){
		   for(int j=0;j<board.getSize();j++){
			   // find the first cell of a new group
			   if(visitedCells.contains(board.getCell(i,j))==false && board.getCell(i,j).getPlayer()==player   ){
				   group=new ArrayList<Cell>();// temp group holder
				   TraverseGroup(board.getCell(i,j),group,visitedCells);
				   groups.add( (ArrayList<Cell>)group.clone() );
			   }
		   }
	   }
	   return groups;
   }
   // recursive function that picks a cell of some color and creates a list of connected same color cells
   private void TraverseGroup(Cell cell,ArrayList<Cell> group,ArrayList<Cell> visitedCells){// recursive helper for getGroups
	   group.add(cell); // add the (starter) cell
	   visitedCells.add(cell);
	   for(Cell nbr : board.getCellNeighbors(cell)  ){
		   if(visitedCells.contains(nbr)==false && nbr.getPlayer()==cell.getPlayer()){
			   TraverseGroup(nbr,group,visitedCells);
		   }
	   }
   }
   
   // just for debugging purposes
   @Override
   public String toString(){
		String retVal="Groups of: "+this.CurrPlayer + "\n";
		
		for(ArrayList<Cell> grp : getGroups(this.CurrPlayer) ){
			 for(Cell c:grp){
				 retVal+="<" + c.getX() + "," + c.getY() +">";
			 }
			 retVal+="\n";
		}
		
		
		return retVal;
	}
}
